package nachos.threads;

import nachos.machine.*;

import java.util.LinkedList;
import java.util.Random;

/**
 * A scheduler that chooses threads using a lottery.
 *
 * <p>
 * A lottery scheduler associates a number of tickets with each thread. When a
 * thread needs to be dequeued, a random lottery is held, among all the tickets
 * of all the threads waiting to be dequeued. The thread that holds the winning
 * ticket is chosen.
 *
 * <p>
 * Note that a lottery scheduler must be able to handle a lot of tickets
 * (sometimes billions), so it is not acceptable to maintain state for every
 * ticket.
 *
 * <p>
 * A lottery scheduler must partially solve the priority inversion problem; in
 * particular, tickets must be transferred through locks, and through joins.
 * Unlike a priority scheduler, these tickets add (as opposed to just taking
 * the maximum).
 */
public class LotteryScheduler extends PriorityScheduler
{

    /**
     * Allocate a new priority scheduler.
     */
    public LotteryScheduler()
    {
        super();
    }

    /**
     * Allocate a new priority thread queue.
     *
     * @param    transferPriority    <tt>true</tt> if this queue should
     * transfer priority from waiting threads
     * to the owning thread.
     * @return a new priority thread queue.
     */
    public ThreadQueue newThreadQueue(boolean transferPriority)
    {
        return new PriorityQueue(transferPriority);
    }

    /**
     * A <tt>ThreadQueue</tt> that sorts threads by priority.
     */
    protected class PriorityQueue extends PriorityScheduler.PriorityQueue
    {
        PriorityQueue(boolean transferPriority)
        {
            super(transferPriority);
        }


        protected PriorityScheduler.ThreadState pickNextThread()
        {
            if (wait.isEmpty())
                return null;
            int totTicket = 0;
            PriorityScheduler.ThreadState[] list = wait.toArray(new PriorityScheduler.ThreadState[wait.size()]);
            for (PriorityScheduler.ThreadState ts : list) {
                totTicket += ts.getEffectivePriority();
            }
            Random random = new Random();

            int randomLottery = random.nextInt(totTicket);

            int t = 0;

            PriorityScheduler.ThreadState toPick = null;

            for (PriorityScheduler.ThreadState ts : list) {
                t += ts.getEffectivePriority();
                if (t >= randomLottery) {
                    toPick = ts;
                    break;
                }

            }
            wait.remove(toPick);
            return toPick;
        }

    }

    /**
     * The scheduling state of a thread. This should include the thread's
     * priority, its effective priority, any objects it owns, and the queue
     * it's waiting for, if any.
     *
     * @see    KThread#schedulingState
     */
    protected class ThreadState extends PriorityScheduler.ThreadState
    {

        public ThreadState(KThread thread)
        {
            super(thread);
        }


        public int calculateEffectivePriority()
        {
            int res = priority;
            for (PriorityScheduler.PriorityQueue acquired : acquiredQueues)
                for (PriorityScheduler.ThreadState ts : acquired.wait)
                    res += ts.effectivePriority;

            return res;
        }

    }
}




